package com.lihepeng.leecode.linkedList;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 请判断一个链表是否为回文链表。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 * <p>
 * 输入: 1->2->2->1
 * 输出: true
 */
public class Solution234 {
    /**
     * 借助于栈结构完成检测
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        boolean isPalindrome = false;
        ListNode node = head;
        while (node != null) {
            stack.push(node);
            node = node.next;
        }
        while (!stack.isEmpty()) {
            ListNode popNode = stack.pop();
            if (popNode.value != head.value) {
                isPalindrome = false;
            }
            head = head.next;
        }
        return isPalindrome;
    }

    /**
     * 将链表数据复制到数组中使用双指针方法进行判断
     *
     * @param head
     * @return
     */
    public boolean isPalindrome01(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int i = 0, j = list.size() - 1;
        while (i <= j) {
            if (list.get(i).value != list.get(j).value) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    ListNode left;
    public boolean isPalindrome02(ListNode head) {
        left = head;
        return travelList(head);
    }
    private boolean travelList(ListNode right){
        if (right ==null) {
            return true;
        }

        boolean res = travelList(right.next);
        // 后续遍历 链表
        res = res && (left.value==right.value);
        left = left.next;
        return res;
    }
    /**
     * 使用栈递归的方案
     */


    @Test
    public void runTest() {
        ListNode head = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(0);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        boolean palindrome = isPalindrome01(head);
        System.out.println(palindrome);
    }
}
